package leetcode.code1894;

public class Solution3 extends Solution1894 {

	@Override
	public int chalkReplacer(int[] chalk, int k) {
		if (chalk[0] > k)
			return 0;
		for (int i = 1; i < chalk.length; i++) {
			chalk[i] += chalk[i - 1];
			if (chalk[i] > k) {
				return i;
			}
		}
		int mod = k % chalk[chalk.length - 1];
		for (int i = 0; i < chalk.length; i++) {
			if (mod < chalk[i]) {
				return i;
			}
		}
//		int ans = -1;
//		int left = 0;
//		int right = chalk.length - 1;
//		while (left <= right) {
//			int m = ((right - left) >> 1) + left;
//			if (chalk[m] == mod) {
//				if (m + 1 < chalk.length) {
//					return m + 1;
//				} else {
//					return 0;
//				}
//			} else if (mod < chalk[m]) {
//				ans = m;
//				right = m - 1;
//			} else {
//				left = m + 1;
//			}
//		}
		return -1;
	}

// 1,3,5,7
	public static void main(String[] args) {
		Solution3 so = new Solution3();
//		so.debug1();
		so.debug2();
//		System.out.println(Integer.MAX_VALUE);
//		System.out.println(Integer.MAX_VALUE + 10000);

	}

}
